The present invention relates to the field of communication networks, and, more particularly, to mobile ad-hoc wireless networks and related methods.
Wireless networks have experienced increased development in the past decade. One of the most rapidly developing areas is mobile ad-hoc networks. Physically, a mobile ad-hoc network includes a number of geographically-distributed, potentially mobile nodes sharing a common radio channel. Compared with other types of networks, such as cellular networks or satellite networks, the most distinctive feature of mobile ad-hoc networks is the lack of any fixed infrastructure. The network may be formed of mobile nodes only, and a network is created xe2x80x9con the flyxe2x80x9d as the nodes transmit with each other. The network does not depend on a particular node and dynamically adjusts as some nodes join or others leave the network.
Because of these unique characteristics, routing protocols for governing data flow within ad-hoc networks are required which can adapt to frequent topology changes. Two basic categories of ad-hoc routing protocols have emerged in recent years, namely reactive or xe2x80x9con-demandxe2x80x9d protocols, and proactive or table-driven protocols. Reactive protocols collect routing information when a particular route is required to a destination in response to a route request. Examples of reactive protocols include ad-hoc on demand distance vector (AODV) routing, dynamic source routing (DSR), and the temporally ordered routing algorithm (TORA).
On the other hand, proactive routing protocols attempt to maintain consistent, up-to-date routing information from each node to every other node in the network. Such protocols typically require each node to maintain one or more tables to store routing information, and they respond to changes in network topology by propagating updates throughout the network to maintain a consistent view of the network. Examples of such proactive routing protocols include destination-sequenced distance-vector (DSDV) routing, which is disclosed in U.S. Pat. No. 5,412,654 to Perkins; the wireless routing protocol (WRP); and clusterhead gateway switch routing (CGSR). A hybrid protocol which uses both proactive and reactive approaches is the zone routing protocol (ZRP), which is disclosed in U.S. Pat. No. 6,304,556 to Haas.
One challenge to the advancement of ad-hoc network development is that of extending such networks to encompass large numbers of nodes. One prior art attempt to do so utilizes xe2x80x9cspinexe2x80x9d routing, such as in the optimal spine routing (OSR) approach disclosed by Das et al. in xe2x80x9cRouting in Ad-Hoc Networks using Minimum Connected Dominating Sets,xe2x80x9dIEEE Int. Conf. On Commun. (ICC ""97), 1997. In this approach, a spine or xe2x80x9cvirtual backbonexe2x80x9d is defined such that each network node is no more than one hop from a spine node. Global topology (link state) is maintained at each spine node, and a link-state routing algorithm is run at each spine node to produce current routes to every destination.
Another related approach is clustered spine routing (CSR), which is disclosed by Das et al. in xe2x80x9cRouting in Ad-Hoc Networks using a Spine,xe2x80x9d IEEE Int. Conf. On Computer Commun. and Networks (IC3N ""97), 1997. this approach is intended to extend the applicability of spine routing to larger network sizes by grouping the nodes in clusters and adding a second hierarchical level to the OSR approach. Yet another approach is known as partial knowledge spine routing (PSR) which is disclosed by Sivakumar et al. in xe2x80x9cThe Clade Vertebrata: Spines and Routing in Ad-Hoc Networks,xe2x80x9d IEEE Symposium On Computer and Commun., 1998.
One common characteristic of each of the above prior art cluster/spine approaches is that they each rely on proactive routing. One potential drawback of proactive routing is that it typically requires a significant amount of routing overhead to maintain optimal routes to all destinations at all times. This problem may become particularly acute when applied to ad-hoc networks including a very large number of nodes.
In view of the foregoing background, it is therefore an object of the present invention to provide a method for sending data in ad-hoc networks that is particularly well suited for networks having a relatively large number of nodes.
This and other objects, features, and advantages in accordance with the present invention are provided by a method for sending data in a wireless ad-hoc network including a plurality of nodes grouped into clusters of nodes and a plurality of wireless links connecting the plurality of nodes, where each cluster has a designated cluster leader node. The method may include sending a cluster-level route request from a source node of a source cluster to a cluster leader node of the source cluster, and determining a cluster-level route between the source cluster and a destination cluster including a destination node responsive to the cluster-level route request and using a plurality of the cluster leader nodes. Further, a node-level route may be determined from the source node to the destination node along the cluster-level route, and each node along the node-level route may store an address of a next node along the node-level route. Additionally, the data may be transferred from the source node to the destination node via the node-level route based upon the addresses of each next node along the node-level route.
More particularly, the method may further include generating a mission data packet comprising an address of the destination node, and transferring may further include transferring the data also based upon the mission data packet. Also, a respective cluster target node may be determined for each cluster along the cluster-level route. Thus, determining the node-level route may include determining a node-level route from the source node to a cluster target node for a next adjacent cluster along the cluster-level route, and determining a node-level route from each cluster target node to a next cluster target node along the cluster-level route.
In addition, each cluster leader node along the cluster-level route may store an address of a next cluster along the cluster-level route. Each cluster target node may also poll its respective cluster leader node for the next cluster address, and each cluster target node may determine the next cluster target node based upon the next cluster address.
The address of the destination node may be stored along with an address of its respective cluster at the cluster leader node for the source cluster. The method may also include indexing the address of the next node along the node-level route stored at the source node by an address of the destination node.
In addition, a plurality of the cluster leader nodes comprising at least the source cluster leader node and the destination cluster leader node may be grouped into a leader node cluster, and a high-level route from the cluster leader node of the source cluster to the cluster leader node of the destination cluster may be determined within the leader node cluster. Further, the cluster-level route may include at least the clusters having respective cluster leader nodes along the high-level route.
Determining the cluster-level route may include determining designated communication links between the cluster leader nodes, and sending a cluster leader node route request from the cluster leader node of the source cluster to the remaining cluster leaders via the designated communication links. Further, a cluster leader node route reply may be returned from the cluster leader node of the destination cluster to the cluster leader node of the source cluster along a delivery route of the cluster leader node route request.
More particularly, at least one of the designated communications links may include a node that is not a cluster leader node. Further, each cluster leader node may store identities of adjacent cluster leader nodes, and sending the cluster leader node route request may include sending the cluster leader node route request from each cluster leader node to its adjacent cluster leader nodes. Also, the adjacent cluster leader nodes may be periodically polled to maintain current addresses therefor. Furthermore, the delivery route may include a least number of cluster leader nodes between the cluster leader nodes of the source and destination clusters. Other path metrics such as delay, link capacities, availability, etc., may also be useful in determining the best route.
A mobile ad-hoc network is also provided according to the present invention and may include a plurality of nodes grouped into clusters of nodes, each cluster having a designated cluster leader node, and a plurality of wireless links connecting said plurality of nodes. The plurality of nodes may send data therebetween as briefly outlined above.